package lib;

import java.util.Arrays;

/**
 * 
 * @author  Igor Covganet
 * @Created Aug 6, 2010
 * 
 * The class is tested and works well.
 * 200 000 points are processed in less than 1 second.
 */
public class ClosestPair {
	public int ind1 = 0, ind2 = 1;
	public long bestDist;
	
	boolean sortByX = true;
	Pair[] ps, tmpPs;
	public void findClosestPair(int[] xs, int[] ys) {
		bestDist = Long.MAX_VALUE;
		sortByX = true;
		
		tmpPs = new Pair[xs.length];
		ps = new Pair[xs.length];
		for(int i = 0; i < ps.length; i++) {
			ps[i] = new Pair(xs[i], ys[i], i);
		}
		
		Arrays.sort(ps);
		getMinDist(0, xs.length - 1);
	}
	
	void getMinDist(int from, int to) {
		bestDist = Long.MAX_VALUE;
		
		if(to - from <= 2) {
			for(int i = from; i < to; i++) {
				for(int j = i + 1; j <= to; j++) {
					long dist = ps[i].distTo(ps[j]);
					if(bestDist > dist) {
						bestDist = dist;
						ind1 = ps[i].ind;
						ind2 = ps[j].ind;
					}
				}
			}
			return;
		}
		
		int med = (to + from) / 2;
		getMinDist(from, med);
		int val1 = ind1;
		int val2 = ind2;
		long valDist = bestDist;
		getMinDist(med + 1, to);
		
		// confront them
		if(bestDist > valDist) {
			bestDist = valDist;
			ind1 = val1;
			ind2 = val2;
		}
		if(bestDist == 0) {
			return;
		}
		
		// get the pairs from close to centerX line in tmpPs pairs and sort them by y
		int tmpInd = 0, med1 = ps[med].x, med2 = ps[med + 1].x;
		double dist = Math.sqrt(bestDist);
		for(int i = med; i >= from; i--) {
			if(ps[i].x - med2 >= dist) {
				break;
			}
			tmpPs[tmpInd++] = ps[i];
		}
		for(int i = med + 1; i <= to; i++) {
			if(ps[i].x - med1 >= dist) {
				break;
			}
			tmpPs[tmpInd++] = ps[i];
		}
		sortByX = false;
		Arrays.sort(tmpPs, 0, tmpInd);
		
		// check for every point from tmpPs the possible candidates in range (y - dist, y + dist)
		int lastInd = 0;
		for(int i = 0; i < tmpInd; i++) {
			while(tmpPs[lastInd].y <= tmpPs[i].y - dist) {
				lastInd++;
			}
			for(int j = lastInd; j < tmpInd; j++) {
				if(tmpPs[j].y >= tmpPs[i].y + dist) {
					break;
				}
				if(tmpPs[i].ind == tmpPs[j].ind) {
					continue;
				}
				
				valDist = tmpPs[i].distTo(tmpPs[j]);
				if(valDist < bestDist) {
					bestDist = valDist;
					ind1 = tmpPs[i].ind;
					ind2 = tmpPs[j].ind;
					dist = Math.sqrt(bestDist);
					if(bestDist == 0) {
						return;
					}
				}
			}
		}
	}
	
	class Pair implements Comparable<Pair> {
		int x, y, ind;
		
		public Pair(int x, int y, int ind) {
			this.x = x;
			this.y = y;
			this.ind = ind;
		}

		@Override
		public int compareTo(Pair o) {
			if(sortByX) {
				if(x != o.x) {
					return x - o.x;
				}
				
				return y - o.y;
			} else {
				if(y != o.y) {
					return y - o.y;
				}
				
				return x - o.x;
			}
		}
		
		public long distTo(Pair p2) {
			return (long)(p2.x - x) * (p2.x - x) + (long)(p2.y - y) * (p2.y - y);
		}
	}
}
